Let $n$ be a positive integer.  The sequence $(x_k)$ is defined by $x_0 = 0,$ $x_1 = 1,$ and
\[x_{k + 2} = \frac{(n - 1) x_{k + 1} - (n - k) x_k}{k + 1}\]for $k \ge 0.$  Find $x_0 + x_1 + x_2 + \dotsb$ as a function of $n.$
Answer: The first few terms are
\begin{align*}
x_2 &= \frac{(n - 1) \cdot 1 - (n - k) \cdot 0}{1} = n - 1, \\
x_3 &= \frac{(n - 1)(n - 1) - (n - 1) \cdot 1}{2} = \frac{(n - 1)(n - 2)}{2}, \\
x_4 &= \frac{(n - 1) \cdot \frac{(n - 1)(n - 2)}{2} - (n - 2)(n - 1)}{3} = \frac{(n - 1)(n - 2)(n - 3)}{6}.
\end{align*}It looks like
\[x_k = \frac{(n - 1)(n - 2) \dotsm (n - k + 1)}{(k - 1)!}\]for $k \ge 2.$  We prove this by induction.

We see that the result holds for $k = 2$ and $k = 3,$ so assume that the result holds for $k = i$ and $k = i + 1$ for some $i \ge 2,$ so
\begin{align*}
x_i &= \frac{(n - 1)(n - 2) \dotsm (n - i + 1)}{(i - 1)!}, \\
x_{i + 1} &= \frac{(n - 1)(n - 2) \dotsm (n - i + 1)(n - i)}{i!}.
\end{align*}Then
\begin{align*}
x_{i + 2} &= \frac{(n - 1) x_{i + 1} - (n - i) x_i}{i + 1} \\
&= \frac{(n - 1) \cdot \frac{(n - 1)(n - 2) \dotsm (n - i + 1)(n - i)}{i!} - (n - i) \cdot \frac{(n - 1)(n - 2) \dotsm (n - i + 1)}{(i - 1)!}}{i + 1} \\
&= \frac{(n - 1)(n - 2) \dotsm (n - i + 1)(n - i)}{(i - 1)!} \cdot \frac{(n - 1)/i - 1}{i + 1} \\
&= \frac{(n - 1)(n - 2) \dotsm (n - i + 1)(n - i)}{(i - 1)!} \cdot \frac{n - 1 - i}{i(i + 1)} \\
&= \frac{(n - 1)(n - 2) \dotsm (n - i + 1)(n - i)(n - i - 1)}{(i + 1)!}.
\end{align*}This completes the induction step.

It follows that
\[x_k = \frac{(n - 1)(n - 2) \dotsm (n - k + 1)}{(k - 1)!} = \frac{(n - 1)!}{(k - 1)! (n - k)!}  =\binom{n - 1}{k - 1}\]for $k \le n,$ and $x_k = 0$ for $k \ge n + 1.$  Therefore,
\[x_0 + x_1 + x_2 + \dotsb = \binom{n - 1}{0} + \binom{n - 1}{1} + \binom{n - 2}{2} + \dots + \binom{n - 1}{n - 1} = \boxed{2^{n - 1}}.\]